# -*- coding: utf-8 -*-

"""剑指 Offer II 019. 最多删除一个字符得到回文
给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

示例 1:
输入: s = "aba"
输出: true

示例 2:
输入: s = "abca"
输出: true
解释: 可以删除 "c" 字符 或者 "b" 字符

示例 3:
输入: s = "abc"
输出: false

提示:
1 <= s.length <= 10^5
s 由小写英文字母组成"""


class Solution:
    def validPalindrome(self, s: str) -> bool:
        def move():
            nonlocal isvalid, left, right
            while True:
                if left > right:
                    isvalid = True
                    break

                if s[left] == s[right]:
                    left += 1
                    right -= 1
                else:
                    break
        
        isvalid = False
        left, right = 0, len(s)-1
        move()

        if not isvalid:
            left_suspend, right_suspend = left, right

            if s[left+1] == s[right]:
                left += 1
                move()

        if not isvalid:
            left, right = left_suspend, right_suspend
            if s[left] == s[right-1]:
                right -= 1
                move()
        
        return isvalid


if __name__ == '__main__':
    so = Solution()
    print(so.validPalindrome('aba'))
    print(so.validPalindrome('abca'))
    print(so.validPalindrome('abc'))
